package com.chb.recursion;

import java.util.ArrayList;
import java.util.List;

/**
 * 面试题 08.06. 汉诺塔问题  https://leetcode-cn.com/problems/hanota-lcci/
 */
public class HanoiTower {
    public static void main(String[] args) {
        List<Integer> A = new ArrayList<Integer>();
        List<Integer> B = new ArrayList<Integer>();
        List<Integer> C = new ArrayList<Integer>();
        A.add(1);
        A.add(2);
        A.add(3);
        A.add(4);
        new HanoiTower().hanota(A, B, C);
        for (int i: C) {
            System.out.println(i);
        }
    }

    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size(), A, B, C);
    }
    public void move(int n, List<Integer> A, List<Integer> B, List<Integer> C) {
        if (n == 1) {
            C.add(A.remove(A.size()-1));
            return;
        }
        move(n-1, A, C, B);
        C.add(A.remove(A.size()-1));
        move(n-1, B, A, C);
    }
}
